首先可以确定的是,如果点权和不为3的倍数,一定不存在合法方案。
记所有点权和为。
容易想到,令 表示以 为根的子树的点权和 , 则有转移:
然后对于点 , 有一个儿子 使得 ,那么我们可以将 切开,然后 。
最后看是否有两个切点即可。
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
const int MAXN = 1000000;
int n , root , sum , a[ MAXN + 5 ] , dp[ MAXN + 5 ];
int v1 , v2;
vector< int > Graph[ MAXN + 5 ];
void dfs( int u , int fa ) {
dp[ u ] = a[ u ];
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
int v = Graph[ u ][ i ];
if( v == fa ) continue;
dfs( v , u ); dp[ u ] += dp[ v ];
if( dp[ v ] == sum / 3 ) {
if( !v1 ) v1 = v;
else if( !v2 ) v2 = v;
dp[ u ] -= dp[ v ];
}
}
}
int main( ) {
scanf("%d",&n);
for( int i = 1 , v ; i <= n ; i ++ ) {
scanf("%d %d",&v,&a[ i ]); sum += a[ i ];
if( !v ) root = i;
else {
Graph[ i ].push_back( v );
Graph[ v ].push_back( i );
}
}
if( sum % 3 ) {
printf("-1");
return 0;
}
dfs( root , 0 );
if( !v1 || !v2 )
printf("-1");
else
printf("%d %d\n",v1,v2);
return 0;
}